#pragma once

#include<iostream>
#include<utility>
#include<vector>
#include<string>
using namespace std;

template<class T>
struct HashData
{
	T _data;
	HashData<T> _next;

	HashData(const T& data)
		:_data(data)
		,next(nullptr)
	{}


};

template<class K>
struct DefaultHashFunc
{
	size_t operator()(const T& key)
	{
		return (size_t)key;
	}
};

template<>
struct DefaultHashFunc <string>
{
	size_t operator()(const string& key)
	{
		size_t hashi = 0;
		for (auto e : key)
		{
			hashi *= 131;
			hashi += e;
		}
		return hashi;
	}
};

template<class K, class T,class HashFunc,class keyofT>
struct HashIterator
{
	typedef HashData<K> Node;
	typedef HashIterator<K, T, HashFunc, keyofT> self;

	Node* _node;
	HashTable<K, T, HashFunc, keyofT>* _pht;

	HashIterator(Node* node, HashTable<K, T, HashFunc, keyofT>* pht)
		:_node(node)
		,_pht(pht)
	{}

	T& operator*()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}

	self& operator++( )
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else
		{
			keyofT kot;
			HashFunc hf;
			size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
			++hashi;
			while (hashi < _pht->_table.size())
			{
				if (_pht == _table[hashi])
				{
					_node = _table[hashi];
					return *this;
				}
				else
				{
					++hashi;
				}

				
			}
			_node = nullptr;

		}
		return *this;
	}

	bool operator != (const self& s)
	{
		return _node != s._node;
	}
	bool operator==(const self& s)
	{
		return _node == s._node;
	}
};

template<class K,class T,class HashFunc = DefaultHashFunc<K> ,class keyofT>
class HashTable
{
	typedef HashIterator<K, T, HashFunc, keyofT> Itreraor;
	typedef HashData< T> Node;
public:
	Itreraor begin()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				return(nullptr, this);
			}
		}
	}
	Iterator end()
	{
		return (nullptr, this);
	}

	HashTable()
	{
		_table.resize(nullptr, 10);
	}
	~HashTable()
	{
		for (int i = 0; i < _table.szie(); i++)
		{
			Node* cur = nullptr;
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_table[i] = nullptr;
		}
	}
	bool Insert(const T& data)
	{
		HashFunc hf;
		keyofT kot;
		if (_n == _table.size())
		{
			size_t newszie = _table.size() * 2;
			vector<Node*> newtable;
			newtable.resize(nullptr, newsize);
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;

					size_t hashi = hf(kot(cur->_data)) % newtable.size();
					cur->next = newtable[hashi];
					newtable[hashi] = cur;

					cur = next;
				}
				_table[i] = nullptr;

			}
			_table.swap(newtable);
		}

		size_t hashi = hf(kot(data)) % _table.size();
		Node* newnode = new Node(data);
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;
		++_n;
		return true;
	}


	Node* Find(const K& key)
	{
		HashFunc hf;
		keyofT kot;
		szie_t hashi = hf(kot(key)) % _table.size();
		Node* cur = _table[hashi];
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				return cur;
			}
			cur = cur->next;
		}
		return nullptr;
	}
	bool Erase(const T& key)
	{
		keyofT kot;
		HashFunc hf;
		szie_t hashi = hf(kot(key)) % _table.size();
		Node* cur = _table[hashi];
		Node* prev = nullptr;
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				if (prev == nullptr)
				{
					_table[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next
				}
				--_n;
				delete cur;

				return true;
			}

			prev = cur;
			cur = cur->next;
		}
		return false;
	}
private:
	vector<Node*> _table;
	size_t _n = 0;
};
